#include<iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int numDecodings(string s) {
        vector<int>dp(s.size(),0);
        dp[0]=1;
        if(s[0]!='0')dp[1]=1;
        for(int i=2;i<s.size();i++)
        {
            if(s[i-1]!='0')dp[i]+=dp[i-1];
            int t=((s[i-2]-'0')*10+s[i-1]-'0');
            if(t>=10&&t<=26)dp[i]+=dp[i-2];
        }
        return dp[s.size()-1];
    }
};